package main

import . "local/algorithm/util"

func deleteNodeInBst(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return root
	}

	if root.Val == val {
		if root.Left == nil && root.Right == nil {
			return nil
		} else if root.Left == nil {
			return root.Right
		} else if root.Right == nil {
			return root.Left
		} else {
			successor := findMinNode(root.Right)
			successor_copy := &TreeNode{Val: successor.Val}
			successor_copy.Left = root.Left
			successor_copy.Right = removeMinNode(root.Right)
			return successor_copy
		}
	} else if val > root.Val {
		root.Right = deleteNodeInBst(root.Right, val)
		return root
	} else {
		root.Left = deleteNodeInBst(root.Left, val)
		return root
	}
}

func findMinNode(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	for root.Left != nil {
		root = root.Left
	}

	return root
}

/*
*
root分为三种情况
root==nil: 直接返回	(实际不可能，因为只有左右节点都存在时才会走到该方法)
root左节点存在: 深入左子树找最小节点，且返回最小节点
root左节点不存在: 那么最小节点就是root，直接返回root.Right
*/
func removeMinNode(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}

	if root.Left != nil {
		root.Left = removeMinNode(root.Left)
	} else {
		tmp := root.Right
		root.Right = nil
		return tmp
	}
}
